/**
 * @program: leetcode005
 * @author: JCM
 * @create: 2022-11-17 14:24
 * @description: 寻找最长回文子串
 **/
public class test {
    //暴力解法
    /*
    public static void main(String[] args) {
        String str = "asjfhjhk";
        String sub = longestPalindrome(str);
        System.out.println(sub);
    }
    //最长回文子串
    private static String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2) return s;
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        //枚举所有长度大于1 的子串 charArray[i...j]
        for(int i = 0; i < len-1; i++) {
            for(int j = i+1; j < len;j++) {
                if(j-i+1 > maxLen && validPalindromic(charArray,i,j)) {
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
    private static boolean validPalindromic(char[] charArray,int left,int right) {
        while (left < right) {
            if(charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
*/
    //中心扩散法
    /*
    public static void main(String[] args) {
        String str = "cbbd";
        String sub = longestPalindrome(str);
        System.out.println(sub);
    }
    private static String longestPalindrome(String s) {
        if(s == null || s.length() < 1) {
            return "";
        }
        int start = 0,end = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s,i,i);
            int len2 = expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len > end - start) {
                start = i-(len-1)/2;
                end = start+len;
            }
        }
        System.out.println(start);
        System.out.println(end);
        return s.substring(start,end);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left-1;
    }
     */
    //动态规划
    public static void main(String[] args) {
        String str = "cbbd";
        String sub = longestPalindrome(str);
        System.out.println(sub);
    }

    private static String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2) return s;
        int maxlen = 1;
        int begin = 0;
        //dp[i][j] 表示 s[i...j] 是否是 回文串
        boolean[][] dp = new boolean[len][len];
        //初始化 长度为1 的子串
        for(int i = 0; i < len ; i++) {
            dp[i][i] = true;
        }
        for(int j = 1; j < len; j++) {
            for(int i = 0; i < j; i++) {
                if(s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                }else {
                    if(j - i < 3) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //dp[i][j] == true 成立，就表示子串s[i...j]是回文。
                if(dp[i][j] && j-i+1> maxlen) {
                    maxlen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxlen);
    }
}
